package Q543

/**
 * 二叉树的直径
 * @author 237387
 * @date 2022.5.12
 */
fun main() {

}

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    var max = 0
    fun diameterOfBinaryTree(root: TreeNode?): Int {
        if (root != null) {
            //遍历每一个节点,求出此节点作为根的树的深度,那么,左子树深度加右子树深度的最大值即是答案
            setDepth(root)
            return max
        }
        return 0
    }

    fun setDepth(root: TreeNode?): Int {
        if (root != null) {
            val right = setDepth(root.right)
            val left = setDepth(root.left)
            if (right + left > max) max = right + left
            return Math.max(right, left) + 1
        }
        return 0
    }
}